<?php

/**
 * 归并排序
 * 时间复杂度:O(n log n)
 *
 * 比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，
 * 并令i和k分别加上1；否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，
 * 如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。
 * 归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，
 * 最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]
 *
 */

class MergeSort
{
    /**
     * 初始化
     *
     * @param array $arr 数组
     *
     * @return array
     */
    public function __construct($arr=[])
    {
        $count = count($arr);
        $this->mergeSort($arr,0,$count-1);
        var_dump($arr);
    }
    
    /**
     * 实现排序过程
     *
     * @param array  $arr       需要排序的数组
     * @param int    $left      子序列的左下标值
     * @param int    $right     子序列的右下标值
     *
     * @return mixed
     */
    public function mergeSort(&$arr,$left,$right)
    {
        if ($left < $right)
        {
            #拆分子数组的元素个数大于一个1个时，就需要拆分，分别排序进行合并
            
            //找到需要拆分的位置
            $conter = floor(($left+$right)/2);
            
            //递归调用左边的进行拆分排序
            $this->mergeSort($arr,$left,$conter);
            
            //递归调用右边的进行拆分排序
            $this->mergeSort($arr,$conter+1,$right);
            
            //合并排序数组
            $this->merge($arr,$left,$conter,$right);
            
        }
    }
    
    /**
     * 将两个有序的数组合并成一个有序数组
     *
     * @param array $arr    数组
     * @param int   $left   排序数组A的开始下标
     * @param int   $conter 排序子数组A和排序子数组B的中间下标同时也A数组的结束下标
     * @param int   $right  排序子数组B的结束下标 起点 $conter+1
     *
     * @return $mid
     */
    public function merge(&$arr,$left,$conter,$right)
    {
        $a = $left;
        $b =  $conter + 1;
        $tmp = [];
        while($a<=$conter && $b<=$right)
        {
            //比较数组a和数组b的元素,将比较的结果赋值给临时数组tmp，同时将比较的下标移位
            if ($arr[$a] < $arr[$b])
            {
                $tmp[] = $arr[$a++];
            }
            else
            {
                $tmp[] = $arr[$b++];
            }
        }

        //判断a数组是否移位完成
        while($a<=$conter)
        {
            $tmp[] = $arr[$a++];
        }

        //同理判断b数组是否移位完成
        while($b<=$right)
        {
            $tmp[] = $arr[$b++];
        }
        
        //将数组tmp排序好的元素写入到$arr
        $len = count($tmp);
        for($i=0;$i<$len;$i++)
        {
            //此时$left为移位的偏移量
            $arr[$left + $i] = $tmp[$i];
        }
        
    }
}
$arr = [1,2,3,43,121,12,-2,1,3,0.2,121,342];
new MergeSort($arr);

